package Year22_Month05.day22;

public class 数组中的第K个最大元素 {
    public int findKthLargest(int[] nums, int k) {
        int end = nums.length - 1;
        //总的思路就是构造一个大根堆，然后不停的删减元素，删除K个之后，此时的0号下标就是要求的
        for (int i = (end - 1) / 2; i >= 0; i--) {
            shiftDowm(nums,i,end);
        }
        //开始删减元素，删减K个之后就结束了
        while(k-- > 1){
            swap(nums,0,end);
            end--;
            shiftDowm(nums,0,end);
        }
        return nums[0];
    }

    public void shiftDowm(int[] nums,int parent,int end){
        //这里是定义的左孩子
        int child = parent * 2 + 1;
        while(child <= end){
            //首先要进行判断，父节点要和左右子树里面大的哪一个进行交换
            if(child + 1 <= end && nums[child] < nums[child + 1]){
                child = child + 1;
            }
            if(nums[child] > nums[parent]){
                swap(nums,parent,child);
                parent = child;
                child = parent * 2 + 1;
            }else{
                break;//如果说当前父节点的值大于子节点，那么就证明当前已经是大根堆，所以停止调整。
            }
        }
    }
    public void swap(int[] nums,int i,int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
